선택 정렬

선택정렬은 데이터의 원소중에 가장 작은 최솟값의 인덱스를 찾은뒤 이를 교환해 주는 방법으로 동작한다. 위의 첫번째 단계를 보면 1이라는 최소 원소를 찾은 뒤 가장 이를 8의 원소의 위치와 교환해 주어 가장 최소의 값을 앞에 위치 시키는 것으로 볼 수 있다. 그 다음 최소값을 찾으면 3을 찾았고 그 다음 최솟값이 위치해야 할 5의 위치와 원소를 바꾸어주었다. 이와 같은 과정을 n-1번 반복하면서 최솟값을 찾는데 약 n의 시간이 소요되므로 O(n2)의 시간복잡도를 가진 정렬이다.

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<ctime>

using namespace std;

void swap(vector<int>& arr, int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void selectionSort(vector<int>& arr)
{
	int m_index;
	for (int i = 0; i < arr.size() - 1; i++)
	{
		m_index = i;
		for (int j = i; j < arr.size(); j++)
		{
			if (arr[j] < arr[m_index])
				m_index = j;
		}
		swap(arr, i, m_index);
	}
}

void main()
{
	srand((unsigned int)time(NULL));

	vector<int> arr;
	for (int i = 0; i < 10; i++)
		arr.push_back(rand() % 100);

	selectionSort(arr);

	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
}